检索结果

期刊

出版年

关键词

Please wait a minute...

选择:

导出引用
EndNote Ris BibTeX

显示/隐藏图片

Select

线性划分问题的一个改进算法

刘金义

辽宁石油化工大学学报 2007, 27 (3): 49-52.

摘要（282）

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列，使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质，给出一个快速改进算法，其时间复杂度为O(knlogn)，空间复杂度为O(n)。